package com.husk.leetcode.dp;

/**
 * <p>
 * 动态规划背包问题
 * <p>
 * 01背包问题
 * 完全背包问题
 * 多重背包问题
 * </p>
 *
 * @author hushunke@sm.vvip-u.com
 * @since 2021/3/26
 */
public class PackageModel {

    /**
     * 01背包问题
     * 一共有N件物品，每件物品只有1个，第i件物品的重量为w[i],价值为v[i]
     * 总重量不超过背包承载上线W的情况下，能够装入的最大价值是多少
     *
     * dp[i][j]表示将前i件物品装进限重为j的背包可获得最大价值，0<=i<=n， 0<=j<=w
     * 1. 不装入第i件物品， dp[i-1][j]
     * 2. 装入第i件物品，dp[i-1][j-w[i]] + v[i]
     *
     * 状态转移方程:
     * dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]), j>w[i];
     * dp[0][0] = 0;
     *
     */

    /**
     * 完全背包问题
     * 每种物品改为无限多个
     *
     * dp[i][j]表示将前i种物品装进限重为j的背包可以获得的最大价值, 0<=i<=n， 0<=j<=w
     * 1. 不装入第i件物品，dp[i-1][j]
     * 2. 装入第i件物品, dp[i-1][j - k * w[i]] + k * v[i]，j>w[i]. w[i] * k < j；
     *
     * 状态转移方程
     * dp[i][j] = max(dp[i-1][j], dp[i-1][j - k * w[i]] + k * v[i]), j>w[i]，k>j/w[i]；
     * dp[0][0] = 0;
     *
     */


}
